/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 无序数组中求最长连续子序列
 * Given [100, 4, 200, 1, 3, 2], 
 * The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
 *  O(n) complexity. 
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月24日
 */
public class LongestConsecutiveSequence {

    public int longestConsecutive(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int max = 1;
        for(int i:nums){
            if(map.containsKey(i)){
                continue;//忽略重复值
            }
            map.put(i, 1);
            if(map.containsKey(i-1)){//连接左边元素
                max = Math.max(max, merge(map,i-1,i));
            }
            if(map.containsKey(i+1)){//连接左边元素
                max = Math.max(max, merge(map,i,i+1));
            }
        }
        return max;
    }

    /**
     * @param map
     * @param left
     * @param right
     * @return
     * @author towan
     * 2015年5月24日
     */
    private int merge(Map<Integer, Integer> map, int left, int right) {
        int upper = right+map.get(right)-1;//最右边数
        int lower = left-map.get(left)+1;//最左边数
        
        int len = upper-lower+1;
        //更新左右边界
        map.put(upper, len);//
        map.put(lower, len);//
        return len;
    }
    public static void main(String[] args) {
        LongestConsecutiveSequence sequence = new LongestConsecutiveSequence();
        int[] nums = {100, 4, 200, 1, 3, 2};
        int max = sequence.longestConsecutive(nums );
        System.out.println(max);
    }
}
